{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #提取咒文"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: extractMantra"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #提取咒文"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "随着兽群逐渐远去，一座大升降机缓缓的从地下升到了远征队面前。借由这台升降机，他们将能够到达地底的永恒至森。\n",
    "在升降机的操作台上，是一个由魔法符号组成的矩阵，为了便于辨识，我们用小写字母来表示。 `matrix[i][j]` 表示矩阵第 `i` 行 `j` 列的字母。该矩阵上有一个提取装置，可以对所在位置的字母提取。\n",
    "提取装置初始位于矩阵的左上角 `[0,0]`，可以通过每次操作移动到上、下、左、右相邻的 1 格位置中。提取装置每次移动或每次提取均记为一次操作。\n",
    "\n",
    "远征队需要按照顺序，从矩阵中逐一取出字母以组成 `mantra`，才能够成功的启动升降机。请返回他们 **最少** 需要消耗的操作次数。如果无法完成提取，返回 `-1`。\n",
    "\n",
    "**注意：**\n",
    "- 提取装置可对同一位置的字母重复提取，每次提取一个\n",
    "- 提取字母时，需按词语顺序依次提取\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`matrix = [\"sd\",\"ep\"], mantra = \"speed\"`\n",
    ">\n",
    ">输出：`10`\n",
    ">\n",
    ">解释：如下图所示\n",
    "![矩阵 (2).gif](https://pic.leetcode-cn.com/1646288670-OTlvAl-%E7%9F%A9%E9%98%B5%20\\(2\\).gif)\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`matrix = [\"abc\",\"daf\",\"geg\"]， mantra = \"sad\"`\n",
    ">\n",
    ">输出：`-1`\n",
    ">\n",
    ">解释：矩阵中不存在 `s` ，无法提取词语\n",
    "\n",
    "**提示：**\n",
    "- `0 < matrix.length, matrix[i].length <= 100`\n",
    "- `0 < mantra.length <= 100`\n",
    "- `matrix 和 mantra` 仅由小写字母组成"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [kjpLFZ](https://leetcode.cn/problems/kjpLFZ/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [kjpLFZ](https://leetcode.cn/problems/kjpLFZ/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"sd\",\"ep\"]\\n\"speed\"', '[\"abc\",\"daf\",\"geg\"]\\n\"sad\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef extractMantra(self, matrix, mantra):\n",
    "\t\tm = len(matrix)\n",
    "\t\tn = len(matrix[0])\n",
    "\t\tpool = set(mantra)\n",
    "\t\tloc = [{char: [] for char in pool} for _ in range(m)]\n",
    "\t\ttmp = [mantra[0]] + [mantra[i] for i in range(1, len(mantra)) if mantra[i] != mantra[i - 1]]\n",
    "\t\tk = len(tmp)\n",
    "\t\texist = set()\n",
    "\t\tfor i in range(m):\n",
    "\t\t\tfor j in range(n):\n",
    "\t\t\t\tif matrix[i][j] in pool:\n",
    "\t\t\t\t\texist.add(matrix[i][j])\n",
    "\t\t\t\t\tloc[i][matrix[i][j]].append(j)\n",
    "\t\tif len(pool) != len(exist):\n",
    "\t\t\treturn -1\n",
    "\t\tmap0 = {(0,0,0): 0} #(第-i个字符, row, col): total step\n",
    "\t\tq = [[0,0,0,0]]\n",
    "\t\twhile q:\n",
    "\t\t\td, i, x, y = heapq.heappop(q)\n",
    "\t\t\tif i + k == 0:\n",
    "\t\t\t\treturn d + len(mantra)\n",
    "\t\t\tif d != map0[(i, x, y)]:\n",
    "\t\t\t\tcontinue\n",
    "\t\t\tl = 0\n",
    "\t\t\tr = n - 1\n",
    "\t\t\tfor x0 in range(x, -1, -1):\n",
    "\t\t\t\tarr = loc[x0][tmp[-i]]\n",
    "\t\t\t\tidx = bisect.bisect_left(arr, y)\n",
    "\t\t\t\tif idx < len(arr) and arr[idx] == y:\n",
    "\t\t\t\t\tself.update(map0, q, (i - 1, x0, y), d + x - x0)\n",
    "\t\t\t\t\tbreak\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tif idx - 1 >= 0 and arr[idx - 1] >= l:\n",
    "\t\t\t\t\t\tself.update(map0, q, (i - 1, x0, arr[idx - 1]), d + x - x0 + y - arr[idx - 1])\n",
    "\t\t\t\t\t\tl = arr[idx - 1] + 1\n",
    "\t\t\t\t\tif idx < len(arr) and arr[idx] <= r:\n",
    "\t\t\t\t\t\tself.update(map0, q, (i - 1, x0, arr[idx]), d + x - x0 + arr[idx] - y)\n",
    "\t\t\t\t\t\tr = arr[idx] - 1\n",
    "\t\t\tl = 0\n",
    "\t\t\tr = n - 1\n",
    "\t\t\tfor x0 in range(x, m):\n",
    "\t\t\t\tarr = loc[x0][tmp[-i]]\n",
    "\t\t\t\tidx = bisect.bisect_left(arr, y)\n",
    "\t\t\t\tif idx < len(arr) and arr[idx] == y:\n",
    "\t\t\t\t\tself.update(map0, q, (i - 1, x0, y), d + x0 - x)\n",
    "\t\t\t\t\tbreak\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tif idx - 1 >= 0 and arr[idx - 1] >= l:\n",
    "\t\t\t\t\t\tself.update(map0, q, (i - 1, x0, arr[idx - 1]), d + x0 - x + y - arr[idx - 1])\n",
    "\t\t\t\t\t\tl = arr[idx - 1] + 1\n",
    "\t\t\t\t\tif idx < len(arr) and arr[idx] <= r:\n",
    "\t\t\t\t\t\tself.update(map0, q, (i - 1, x0, arr[idx]), d + x0 - x + arr[idx] - y)\n",
    "\t\t\t\t\t\tr = arr[idx] - 1\n",
    "\t\n",
    "\tdef update(self, map0, q, key, val):\n",
    "\t\tif val < map0.get(key, float('inf')):\n",
    "\t\t\tmap0[key] = val\n",
    "\t\t\theapq.heappush(q, [val] + list(key))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n, l = len(matrix), len(matrix[0]), len(mantra)\n",
    "        q, head = [[0, 0, 0]], -1\n",
    "        num_ops = [0]\n",
    "        visited = [[[False] * (l + 1) for _ in range(n)] for __ in range(m)]\n",
    "        visited[0][0][0] = True\n",
    "        while head + 1 < len(q):\n",
    "            head += 1\n",
    "            x, y, k = q[head]\n",
    "            if k == l:\n",
    "                return num_ops[head]\n",
    "            if matrix[x][y] == mantra[k] and not visited[x][y][k + 1]:\n",
    "                q.append([x, y, k + 1])\n",
    "                visited[x][y][k + 1] = True\n",
    "                num_ops.append(num_ops[head] + 1)\n",
    "            for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                xx, yy = x + d[0], y + d[1]\n",
    "                if xx < 0 or xx >= m or yy < 0 or yy >= n or visited[xx][yy][k]:\n",
    "                    continue\n",
    "                q.append([xx, yy, k])\n",
    "                visited[xx][yy][k] = True\n",
    "                num_ops.append(num_ops[head] + 1)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n, l = len(matrix), len(matrix[0]), len(mantra)\n",
    "        q, head = [[0, 0, 0]], -1\n",
    "        num_ops = [0]\n",
    "        visited = [[[False] * (l + 1) for _ in range(n)] for __ in range(m)]\n",
    "        visited[0][0][0] = True\n",
    "        while head + 1 < len(q):\n",
    "            head += 1\n",
    "            x, y, k = q[head]\n",
    "            if matrix[x][y] == mantra[k] and not visited[x][y][k + 1]:\n",
    "                if k + 1 == l:\n",
    "                    return num_ops[head] + 1\n",
    "                q.append([x, y, k + 1])\n",
    "                visited[x][y][k + 1] = True\n",
    "                num_ops.append(num_ops[head] + 1)\n",
    "            for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                xx, yy = x + d[0], y + d[1]\n",
    "                if xx < 0 or xx >= m or yy < 0 or yy >= n or visited[xx][yy][k]:\n",
    "                    continue\n",
    "                q.append([xx, yy, k])\n",
    "                visited[xx][yy][k] = True\n",
    "                num_ops.append(num_ops[head] + 1)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])        \n",
    "        step, q, vis = 1, [(0, 0, 0)], set()\n",
    "\n",
    "        while q:\n",
    "            nxt = []\n",
    "            for i, j, idx in q:\n",
    "                if matrix[i][j] == mantra[idx]:\n",
    "                    if idx == len(mantra) - 1:\n",
    "                        return step\n",
    "                    if (node := (i, j, idx + 1)) not in vis:\n",
    "                        nxt.append(node)\n",
    "                        vis.add(node)\n",
    "\n",
    "                for ni, nj in [[i, j - 1], [i, j + 1], [i - 1, j], [i + 1, j]]:\n",
    "                    if 0 <= ni < m and 0 <= nj < n:\n",
    "                        if (node := (ni, nj, idx)) not in vis:\n",
    "                            nxt.append(node)\n",
    "                            vis.add(node)\n",
    "            q = nxt\n",
    "            step += 1\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        # 起点，q代表当前可达且不在已访问节点，x,y,z分别为行数、列数、第几个要到达的字母\n",
    "        #（即mantra中的第几个字母）\n",
    "        q = [(0, 0, 0)]\n",
    "        # vis为已访问节点\n",
    "        vis = {q[0]}\n",
    "        # 花费的步数\n",
    "        step = 1\n",
    "\n",
    "        while q:\n",
    "            # 当前可能在的节点\n",
    "            tmp = q\n",
    "            # 清空q用于储存下一步可能访问的节点\n",
    "            q = []\n",
    "            for i, j, k in tmp:\n",
    "                # 到达要访问的字母\n",
    "                if matrix[i][j] == mantra[k]:\n",
    "                    # 退出条件：到达终点\n",
    "                    if k == len(mantra)-1:\n",
    "                        return step\n",
    "                    # 开始下一个节点的访问，从当前位置开始，如果vis中没有该点，则加入q和vis\n",
    "                    p = (i, j ,k+1)\n",
    "                    if p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                # 没有到达要访问的字母，则下一步可能访问的节点为当前访问节点的周围点\n",
    "                # 如果周围点已经存在vis中，则无需访问该节点（因为已有更快的路径到达该点）\n",
    "                for x,y in (i + 1, j), (i, j + 1),(i - 1, j), (i, j - 1):\n",
    "                    if 0 <= x <m and 0 <= y < n:\n",
    "                        p = (x, y, k)\n",
    "                        if p not in vis:\n",
    "                            vis.add(p)\n",
    "                            q.append(p)\n",
    "            # 当前访问节点的所有情况均处理完成，则开始对下一步访问的节点重复该过程\n",
    "            step += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        q = [(0, 0, 0)]\n",
    "        vis = {q[0]}\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j, k in tmp:\n",
    "                if matrix[i][j] == mantra[k]:  # 可以提取\n",
    "                    if k == len(mantra) - 1:  # 下一步就是终点，直接返回\n",
    "                        return step\n",
    "                    p = (i, j, k + 1)\n",
    "                    # if p is in vis, it means we have reached state p previously. going through the route again won't provide a better result. \n",
    "                    if p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                # 枚举周围四个格子\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        p = (x, y, k)\n",
    "                        if p not in vis:\n",
    "                            vis.add(p)\n",
    "                            q.append(p)\n",
    "            step += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        q = [(0, 0, 0)]\n",
    "        vis = {q[0]}\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j, k in tmp:\n",
    "                if matrix[i][j] == mantra[k]:  # 可以提取\n",
    "                    if k == len(mantra) - 1:  # 下一步就是终点，直接返回\n",
    "                        return step\n",
    "                    p = (i, j, k + 1)\n",
    "                    if p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                # 枚举周围四个格子\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        p = (x, y, k)\n",
    "                        if p not in vis:\n",
    "                            vis.add(p)\n",
    "                            q.append(p)\n",
    "            step += 1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        q = [(0, 0, 0)]\n",
    "        vis = {q[0]}\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j, k in tmp:\n",
    "                if matrix[i][j] == mantra[k]:  # 可以提取\n",
    "                    if k == len(mantra) - 1:  # 下一步就是终点，直接返回\n",
    "                        return step\n",
    "                    p = (i, j, k + 1)\n",
    "                    if p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                # 枚举周围四个格子\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        p = (x, y, k)\n",
    "                        if p not in vis:\n",
    "                            vis.add(p)\n",
    "                            q.append(p)\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        q = [(0, 0, 0)]\n",
    "        vis = {q[0]}\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j, k in tmp:\n",
    "                if matrix[i][j] == mantra[k]:  # 可以提取\n",
    "                    if k == len(mantra) - 1:  # 下一步就是终点，直接返回\n",
    "                        return step\n",
    "                    p = (i, j, k + 1)\n",
    "                    if p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                # 枚举周围四个格子\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        p = (x, y, k)\n",
    "                        if p not in vis:\n",
    "                            vis.add(p)\n",
    "                            q.append(p)\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        \n",
    "        step = 1\n",
    "        q = [(0, 0, 0)]\n",
    "        vis = set()\n",
    "\n",
    "        while q:\n",
    "            nxt = []\n",
    "            for i, j, idx in q:\n",
    "                if matrix[i][j] == mantra[idx]:\n",
    "                    if idx == len(mantra) - 1:\n",
    "                        return step\n",
    "                    if (i, j, idx + 1) not in vis:\n",
    "                        nxt.append((i, j, idx + 1))\n",
    "                        vis.add((i, j, idx + 1))\n",
    "\n",
    "                for ni, nj in [[i, j - 1], [i, j + 1], [i - 1, j], [i + 1, j]]:\n",
    "                    if 0 <= ni < m and 0 <= nj < n:\n",
    "                        node = (ni, nj, idx)\n",
    "                        if node not in vis:\n",
    "                            nxt.append(node)\n",
    "                            vis.add(node)\n",
    "            q = nxt\n",
    "            step += 1\n",
    "\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        q = [(0, 0, 0)]\n",
    "        vis = {q[0]}\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j, k in tmp:\n",
    "                if matrix[i][j] == mantra[k]:  # 可以提取\n",
    "                    if k == len(mantra) - 1:  # 下一步就是终点，直接返回\n",
    "                        return step\n",
    "                    p = (i, j, k + 1)\n",
    "                    if p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                # 枚举周围四个格子\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        p = (x, y, k)\n",
    "                        if p not in vis:\n",
    "                            vis.add(p)\n",
    "                            q.append(p)\n",
    "            step += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        q = [(0, 0, 0)]\n",
    "        vis = {q[0]}\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j, k in tmp:\n",
    "                if matrix[i][j] == mantra[k]:  # 可以提取\n",
    "                    if k == len(mantra) - 1:  # 下一步就是终点，直接返回\n",
    "                        return step\n",
    "                    p = (i, j, k + 1)\n",
    "                    if p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                # 枚举周围四个格子\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        p = (x, y, k)\n",
    "                        if p not in vis:\n",
    "                            vis.add(p)\n",
    "                            q.append(p)\n",
    "            step += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        q = [(0, 0, 0)]\n",
    "        vis = {q[0]}\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j, k in tmp:\n",
    "                if matrix[i][j] == mantra[k]:  # 可以提取\n",
    "                    if k == len(mantra) - 1:  # 下一步就是终点，直接返回\n",
    "                        return step\n",
    "                    p = (i, j, k + 1)\n",
    "                    # if p is in vis, it means we have reached state p previously. going through the route again won't provide a better result. \n",
    "                    if p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                # 枚举周围四个格子\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        p = (x, y, k)\n",
    "                        if p not in vis:\n",
    "                            vis.add(p)\n",
    "                            q.append(p)\n",
    "            step += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        q = [(0, 0, 0)]\n",
    "        vis = {q[0]}\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j, k in tmp:\n",
    "                if matrix[i][j] == mantra[k]:  # 可以提取\n",
    "                    if k == len(mantra) - 1:  # 下一步就是终点，直接返回\n",
    "                        return step\n",
    "                    p = (i, j, k + 1)\n",
    "                    # if p is in vis, it means we have reached state p previously. going through the route again won't provide a better result. \n",
    "                    if p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                # 枚举周围四个格子\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        p = (x, y, k)\n",
    "                        if p not in vis:\n",
    "                            vis.add(p)\n",
    "                            q.append(p)\n",
    "            step += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        q = [(0, 0, 0)]\n",
    "        vis = {q[0]}\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j, k in tmp:\n",
    "                if matrix[i][j] == mantra[k]:  # 可以提取\n",
    "                    if k == len(mantra) - 1:  # 下一步就是终点，直接返回\n",
    "                        return step\n",
    "                    p = (i, j, k + 1)\n",
    "                    if p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                # 枚举周围四个格子\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        p = (x, y, k)\n",
    "                        if p not in vis:\n",
    "                            vis.add(p)\n",
    "                            q.append(p)\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        q = [(0, 0, 0)]\n",
    "        vis = {q[0]}\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j, k in tmp:\n",
    "                if matrix[i][j] == mantra[k]:  # 可以提取\n",
    "                    if k == len(mantra) - 1:  # 下一步就是终点，直接返回\n",
    "                        return step\n",
    "                    p = (i, j, k + 1)\n",
    "                    if p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                # 枚举周围四个格子\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        p = (x, y, k)\n",
    "                        if p not in vis:\n",
    "                            vis.add(p)\n",
    "                            q.append(p)\n",
    "            step += 1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        q = [(0, 0, 0)]\n",
    "        vis = {q[0]}\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j, k in tmp:\n",
    "                if matrix[i][j] == mantra[k]:  # 可以提取\n",
    "                    if k == len(mantra) - 1:  # 下一步就是终点，直接返回\n",
    "                        return step\n",
    "                    p = (i, j, k + 1)\n",
    "                    if p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                # 枚举周围四个格子\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        p = (x, y, k)\n",
    "                        if p not in vis:\n",
    "                            vis.add(p)\n",
    "                            q.append(p)\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        q = [(0, 0, 0)]\n",
    "        step = 1\n",
    "        vis = set()\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j, k in tmp:\n",
    "                if matrix[i][j] == mantra[k]:\n",
    "                    if k == len(mantra) - 1:\n",
    "                        return step\n",
    "                    p = (i, j , k+1)\n",
    "                    if p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                for x, y, j in [(i,j-1,k),(i,j+1,k),(i-1,j,k),(i+1,j,k)]:\n",
    "                    if 0<=x<n and 0<=y<m :\n",
    "                        p = (x,y,j)\n",
    "                        if p not in vis :\n",
    "                            vis.add(p)\n",
    "                            q.append(p)\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m,n =len(matrix),len(matrix[0])\n",
    "        q = [(0,0,0)]\n",
    "        vis = {q[0]}\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = q \n",
    "            q = []\n",
    "            for i,j,k in tmp:\n",
    "                if matrix[i][j]== mantra[k]:\n",
    "                    if k==len(mantra)-1:\n",
    "                        return step\n",
    "                    p = (i,j,k+1)\n",
    "                    if p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        p = (x,y,k)\n",
    "                        if p not in vis:\n",
    "                            vis.add(p)\n",
    "                            q.append(p)\n",
    "            step +=1                            \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        q = [(0, 0, 0)]\n",
    "        vis = {q[0]}\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j, k in tmp:\n",
    "                if matrix[i][j] == mantra[k]:  # 可以提取\n",
    "                    if k == len(mantra) - 1:  # 下一步就是终点，直接返回\n",
    "                        return step\n",
    "                    p = (i, j, k + 1)\n",
    "                    if p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                # 枚举周围四个格子\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        p = (x, y, k)\n",
    "                        if p not in vis:\n",
    "                            vis.add(p)\n",
    "                            q.append(p)\n",
    "            step += 1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def extractMantra(self, matrix: List[str], mantra: str) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        q = [(0, 0, 0)]  # i, j, k 分别表示当前位置的行、列和已完成的mantra长度\n",
    "        vis = {q[0]}  # 已访问过的状态集合\n",
    "        step = 1  # 步数，即操作次数\n",
    "        \n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j, k in tmp:\n",
    "                # 检查当前位置是否可以提取字母\n",
    "                if matrix[i][j] == mantra[k]:\n",
    "                    if k == len(mantra) - 1:  # 如果是最后一个字母，直接返回步数\n",
    "                        return step\n",
    "                    p = (i, j, k + 1)  # 否则更新已完成的mantra长度\n",
    "                    if p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                        \n",
    "                # 枚举四个相邻格子，并加入队列中\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        p = (x, y, k)\n",
    "                        if p not in vis:\n",
    "                            vis.add(p)\n",
    "                            q.append(p)\n",
    "                            \n",
    "            step += 1  # 每完成一层搜索，步数加1\n",
    "            \n",
    "        return -1  # 如果搜索结束后还没找到解，返回-1\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
